Hash Table
https://gyazo.com/03f3096c3d80ad006e9bdbcb0da1d3a3 https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E3%83%86%E3%83%BC%E3%83%96%E3%83%AB#:~:text=%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E3%83%86%E3%83%BC%E3%83%96%E3%83%AB%20(%E8%8B%B1%3A%20hash%20table,%E3%81%86%E3%81%A11%E3%81%A4%E3%81%A7%E3%81%82%E3%82%8B%E3%80%82
ハッシュテーブルはキーをもとに生成されたハッシュ値を添え字とした配列である。 ref 通常、配列の添え字には非負整数しか扱えない。
そこで、キーを要約する値であるハッシュ値を添え字として値を管理することで、検索や追加を要素数によらず定数時間O(1)で実現する。 しかしハッシュ関数の選び方（例えば、異なるキーから頻繁に同じハッシュ値が生成される場合）によっては、性能が劣化して最悪の場合O(n)となってしまう。 Hash Tableのサイズは素数にすると衝突が起きづらく効率が良い GPT-4.iconの直観的な例
### 例1: サイズが素数ではない場合
ハッシュテーブルのサイズが64（素数ではない）で、ハッシュ関数は以下のように定義します：
$ \text{スロット番号} = \text{キーの値} \mod 64
例えば、以下のキーをハッシュテーブルに挿入する場合を考えます：
- キー1: 100
- キー2: 164
- キー3: 228
- キー4: 292
これらのキーをハッシュ関数に通すと、スロット番号は次のようになります：
$ 100 \mod 64 = 36
$ 164 \mod 64 = 36
$ 228 \mod 64 = 36
$ 292 \mod 64 = 36
すべてのキーが同じスロット番号36に割り当てられ、衝突が発生します。この場合、スロット番号の範囲が小さく、特定のパターンが繰り返されるため、衝突が頻発する可能性が高くなります。
### 例2: サイズが素数の場合
ハッシュテーブルのサイズを67（素数）に変更し、同じハッシュ関数を使用します：
$ \text{スロット番号} = \text{キーの値} \mod 67
同じキーをハッシュ関数に通すと、スロット番号は次のようになります：
$ 100 \mod 67 = 33
$ 164 \mod 67 = 30
$ 228 \mod 67 = 27
$ 292 \mod 67 = 24
異なるスロット番号にキーが割り当てられ、衝突が発生しません。素数を使用することで、キーが均等に分散され、衝突が減少します。